#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


// class Solution {
// public:
//     ListNode* mergeKLists(vector<ListNode*>& lists) {
//         int K = lists.size();
//         int temp_value1, temp_value2, temp_value3;
//         while ()
//         {
//             /* code */
//         }
        
//     }
// };

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int K = lists.size();
        // 基本情况处理
        if (K == 0) return nullptr;
        if (K == 1) return lists[0];
        
        // 递归地将链表数组分成两部分
        int mid = K / 2;
        vector<ListNode*> left(lists.begin(), lists.begin() + mid);
        vector<ListNode*> right(lists.begin() + mid, lists.end());
        
        // 递归合并左右两部分
        ListNode* left_merged = mergeKLists(left);
        ListNode* right_merged = mergeKLists(right);
        
        // 合并两个已排序链表
        return merge_two_list(left_merged, right_merged);
        
    }

    ListNode* merge_two_list(ListNode* head1, ListNode* head2){
        if (head1 == nullptr) return head2;
        if (head2 == nullptr) return head1;
        ListNode temp_node = ListNode();
        ListNode* temp_pointer = &temp_node;
        int value1, value2;
        while (head1 != nullptr && head2 != nullptr) {
            value1 = head1->val;
            value2 = head2->val;
            if (value1 > value2) {
                temp_pointer->next = head2;
                head2 = head2->next;
                temp_pointer = temp_pointer->next;

            }
            else {
                temp_pointer->next = head1;
                head1 = head1->next;
                temp_pointer = temp_pointer->next;
            }
        }
        if (head1 == nullptr) {
            temp_pointer->next = head2;
        }
        else {
            temp_pointer->next = head1;
        }

        return temp_node.next;

        
    }
};